package com.cg.leetcode;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 491.递增子序列
 *
 * @author cg
 * @program LeetCode->LeetCode_491
 * @create 2022-08-29 13:55
 **/
public class LeetCode_491 {

    @Test
    public void test491() {
        System.out.println(findSubsequences(new int[]{4, 6, 7, 7}));
        System.out.println(findSubsequences(new int[]{4, 4, 3, 2, 1}));
    }

    /**
     * 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
     * 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
     * <p>
     * 示例 1：
     * 输入：nums = [4,6,7,7]
     * 输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
     * <p>
     * 示例 2：
     * 输入：nums = [4,4,3,2,1]
     * 输出：[[4,4]]
     * <p>
     * 提示：
     * 1 <= nums.length <= 15
     * -100 <= nums[i] <= 100
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> findSubsequences(int[] nums) {
        result = new ArrayList<>();
        path = new ArrayList<>();
        helper(nums, 0);
        return result;
    }

    List<List<Integer>> result;
    List<Integer> path;

    private void helper(int[] nums, int startIndex) {
        if (path.size() > 1) {
            result.add(new ArrayList<>(path));
        }
        int[] used = new int[201];
        for (int i = startIndex; i < nums.length; i++) {
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1)) {
                continue;
            }
            if (used[nums[i] + 100] == 1) {
                continue;
            }
            used[nums[i] + 100] = 1;
            path.add(nums[i]);
            helper(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }

}
